package queue;

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.List;

class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode() {}
  TreeNode(int val) { this.val = val; }
  TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
  }
}

public class WidthOfBinaryTree {
    public int code(TreeNode root) {
        List<Pair<TreeNode, Integer>> q = new ArrayList<>();
        q.add(new Pair<>(root, 1));
        int ret = 0;

        while (!q.isEmpty()){
            Pair<TreeNode, Integer> t1 = q.get(0);
            Pair<TreeNode, Integer> t2 = q.get(q.size() - 1);
            ret = Math.max(ret, t2.getValue() - t1.getValue() + 1);

            List<Pair<TreeNode, Integer>> tmp = new ArrayList<>();
            for (Pair<TreeNode, Integer> t : q){
                TreeNode node = t.getKey();
                int index = t.getValue();

                if (node.left != null){
                    tmp.add(new Pair<TreeNode, Integer>(node.left, index * 2));
                }

                if (node.right != null){
                    tmp.add(new Pair<TreeNode, Integer>(node.right, index * 2 + 1));
                }

                q = tmp;
            }


        }
        return ret;
    }
}
